package q844_backspaceCompare;

public class Solution_2 {
    /*
    比较含有退格的字符串
    对于o(1)空间复杂度的做法
    则需要在两个字符串最后都维护一个指针 每当指针遇到#时 则需要将skip + 1
    当我们遍历到字母时，如果skip = 0 则可以比较两个指针指向的字母是否相等 不相等则返回false
    如果skip > 0 则skip-- 并且跳过该字符
     */
    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (S.charAt(i) != T.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;

    }
}
